# -*- coding: utf-8 -*-
'''
projecto- classe destinada ao algoritmo de ordenação: merge sort
autor- Ana Isabel Marques 6052
data de criação do módulo- 30/05/2013

Complexidade Computacional:
        pior caso - O(n log(n))
        caso médio - O(n log(n))
        melhor caso - O(n log(n))
        
'''

import sys
import math

class MergeSort:
        
        '''
        Constructor
        @param A - lista de números inteiros
        '''
        def __init__(self, A):
                self.A = A
                pass
        '''
        Calcula a dimensão da parte esquerda e da parte direita da sublista
        @param p 
        @param q 
        @param r
        Os parâmetros p, q e r são índices de A de modo que p<=q<r
        '''
        def merge(self, p, q, r):
                  
                n1 = q - p + 1
                n2 = r - q
                
                L = [self.A[k] for k in xrange (0 , n1)]
                R = [self.A[k] for k in xrange (q + 1 , r + 1)]

                for i in range (0, n1):
                        L[i] = self.A[p + i]
                        pass
                
                for j in range (0, n2):
                        R[j] = self.A[q + j + 1]
                        pass
                
                L.append(sys.maxint)
                R.append(sys.maxint)
                
                i = 0
                j = 0
                
                for k in range (p, r + 1 ):
                        if L[i] <= R[j]:
                                self.A[k] = L[i]
                                i = i + 1
                                pass
                        
                        else:
                                self.A[k] = R[j]
                                j = j + 1
                                pass
                        pass

                pass

        '''
        Ordena uma lista através do algoritmo de ordenação:
        merge sort
        @param p - índice 0 da lista
        @param r - tamanho da lista menos um para não dar overflow ao percorrer
        a A. (len(A)-1)
        '''
        def merge_sort(self, p, r):
                
                if p < r:
                        q = int(math.floor((p + r)/2.0))
                        self.merge_sort(p, q)
                        self.merge_sort(q + 1, r)
                        self.merge(p, q, r)

                        pass
                pass
        pass
pass
